import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:张熳
 * Date:2025-10-09
 * Time:20:40
 */

//单链表练习题
public class MySingleList {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;

    public void addLast(int date) {
        ListNode node = new ListNode(date);
        if (head == null) {
            head = node;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
    public int size() {
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        return len;
    }
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //移除链表元素
    //给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
    public ListNode removeElements(int val) {
        if (head == null) {
            return null;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }
    //反转链表
    //给你一个单链表的头节点 head ，请你反转链表，并返回反转后的链表（只遍历链表一遍，同时在链表本身上进行修改）——头插法
    public ListNode reverseList() {
        if (head == null) {
            return null;
        }
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
    public void display2(ListNode newHead) {
        ListNode cur = newHead;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    //链表的中间节点
    //给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点 —— 快慢指针（奇数和偶数节点情况）
    public ListNode middleNode() {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    //返回链表倒数第k个节点 —— 快慢指针
    //输入一个单链表，找出单链表中倒数第k个节点，返回该节点的值（保证k必须有效）
    public int kthToList(int k) {
        if (head == null) {
            return -1;
        }
        //判断k是否有效（如果题目中已经说明k一定是有效的，就不必写这一段代码）
        //这是要求链表长度的写法：
        /*if (k <= 0 || k > size()) {
            return -1;
        }*/
        //不求链表长度的写法
        if (k <= 0) {
            return -1;
        }
        ListNode fast = head;
        ListNode slow = head;
        int count = 0;
        while (count != k-1) {
            fast = fast.next;
            //这里是代替 k > size()情况的写法：
            if (fast == null) {
                return -1;
            }
            count++;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
    //合并两个有序链表
    //将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
    public ListNode mergeTwoList(ListNode headA,ListNode headB) {
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while (headA != null && headB != null) {
            if (headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            }else {
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }
        }
        if (headA != null) {
            tmp.next = headA;
        }
        if (headB != null) {
            tmp.next = headB;
        }
        return newHead.next;
    }
    //分割链表
    //给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前
    //且不能改变原来的数据顺序，返回重新排列后的链表的头节点。
    public ListNode partition(int x) {
        ListNode beforeStart = null;
        ListNode beforeEnd = null;
        ListNode afterStart = null;
        ListNode afterEnd = null;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x) {
                if (beforeStart == null) { //第一次插入
                    beforeStart = beforeEnd = cur;
                }else {
                    beforeEnd.next = cur;
                    beforeEnd = beforeEnd.next;
                }
            }else {
                if (afterStart == null) { //第一次插入
                    afterStart = afterEnd = cur;
                }else {
                    afterEnd.next = cur;
                    afterEnd = afterEnd.next;
                }
            }
            cur = cur.next;
        }
        //如果全部的节点中的值都是大于x的，则返回afterStart
        if (beforeStart == null) {
            return afterStart;
        }
        //有小于也有大于，将存放值小于x节点的链表和存放值大于x的链表连接起来
        beforeEnd.next = afterStart;
        //如果afterStart中有节点，那么将afterEnd的next节点置为null，防止陷入循环
        if (afterStart != null) {
            afterEnd.next = null;
        }
        return beforeStart;
    }
    //回文链表
    //编写一个方法，检查输入的链表是否是回文的，给定一个链表的头节点head，请返回一个boolean值，代表其是否为回文结构
    //该方法设计为一个时间复杂度为O(n),额外空间复杂度为O(1)——即不能额外申请空间 的算法
    public boolean isPalindrome() {
        if (head == null) {
            return true;//空链表通常被认为是回文
        }
        ListNode fast = head;
        ListNode slow = head;
        //1.找中间节点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //此时slow指向的就是中间节点
        //2.进行翻转
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //3.判断回文
        while (head != slow) {
            if (head.val != slow.val) {
                return false;
            }
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    //相交链表
    //给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null
    public static ListNode getIntersectionNode(ListNode headA,ListNode headB) {
        //默认长链表longList放的是headA，短链表shortList放的是headB
        ListNode longList = headA;
        ListNode shortList = headB;
        //1.先求2个链表的长度
        int lenA = 0;
        int lenB = 0;
        while (longList != null) {
            lenA++;
            longList = longList.next;
        }
        while (shortList != null) {
            lenB++;
            shortList = shortList.next;
        }
        //求完长度后，longList和shortList重新指向头节点，方便进行其他的操作
        longList = headA;
        shortList = headB;
        //2.求两个链表长度的差值
        int len = lenA - lenB; // 如果len>0,表示headA链表长，不需要修改
        if (len < 0) { //表示headB链表长
            longList = headB;//将headB链表改放在longList长链表中
            shortList = headA;//将headA链表改放在shortList短链表中
            len = lenB - lenA;//将相减的式子交换位置，让其结果变成大于0的情况
        }
        //走完上述第2步，longList一定指向最长链表，shortList一定指向最短链表
        //接下来的操作 只需要操作longList 和 shortList 就行了
        //3.让最长的链表 走len步
        while (len != 0) {
            longList = longList.next;
            len--;
        }
        //4.两个引用同时往后走，直到它们相遇
        while (longList != shortList) {
            longList = longList.next;
            shortList = shortList.next;
        }
        if (longList == null) {
            return null;//没有相交
        }
        return longList;
    }
    //环形链表 —— 快慢指针
    //给你一个链表的头节点 head ，判断链表中是否有环。
    //如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
    //如果链表中存在环，则返回 true 。 否则，返回 false 。
    public boolean hasCycle() {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
    //创建环形
    public void createLoop() {
        ListNode cur = head;
        //找尾
        while (cur.next != null) {
            cur = cur.next;
        }
        //创建环形/圆圈
        cur.next = head.next.next;
    }
    //环形链表II —— 快慢指针
    //给定一个链表的头节点，返回链表开始入环的第一个节点。如果链表无环，则返回null。
    //如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。不允许修改链表
    public ListNode detectCycle() {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;//相遇，表示有环，跳出循环
            }
        }
        if (fast == null || fast.next == null) {
            return null;//没有环
        }
        slow = head;//slow从头节点开始，而fast在相遇点开始，slow和fast同时向入环点一步步走
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;//返回入环点
    }
}
